package dp.multi;

public class Solution_5 {

    /**
     * 一、为什么选二维 DP？
     * 回文串的天然结构是「左右对称」，因此最方便的信息就是 两端字符相等 + 去掉两端仍是回文。
     * 设  s[i…j]  为子串，其回文性质同时依赖
     * 左端字符  s[i]
     * 右端字符  s[j]
     * 内部子串  s[i+1…j-1]
     * 于是需要 两个维度 —— 左端点  i  和右端点  j  —— 才能完整刻画状态
     */
    public String longestPalindrome(String s) {
        int n = s.length();
        if (n < 2) return s;
        boolean[][] dp = new boolean[n][n];
        int start = 0, maxLen = 1;
        for (int i = 0; i < n; i++) {
            dp[i][i] = true;
        }
        for (int len = 2; len <= n; len++) {
            for (int i = 0; i + len - 1 < n; i++) {
                int j = i + len - 1;
                if (s.charAt(i) == s.charAt(j)) {
                    dp[i][j] = (len == 2) || dp[i + 1][j - 1];
                    if (dp[i][j] && len > maxLen) {
                        start = i;
                        maxLen = len;
                    }
                }
            }
        }
        return s.substring(start, start + maxLen);
    }
}
